# 实现方式我们可以进行一个比喻的操作会比较好。
def bubble_sort(arr):
    for j in range(len(arr)):
        for i in range(1, len(arr) - j):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]


def select_sort(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[min_index] > arr[j]:
                min_index = j
        arr[min_index], arr[i] = arr[i], arr[min_index]


def insert_sort(arr):
    for i in range(1, len(arr)):
        start_index = i
        while start_index > 0 and arr[start_index] < arr[start_index - 1]:
            arr[start_index], arr[start_index - 1] = arr[start_index - 1], arr[start_index]
            start_index -= 1


def quick_sort(arr, low, high):
    # 递归操作减轻执行复杂度
    if low > high:
        return
    i = low - 1
    pivot = arr[high]
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    quick_sort(arr, low, i)
    quick_sort(arr, i + 2, high)


if __name__ == '__main__':
    array = [1, 4, 33, 2, 23, 12, 43, 89, 5]
    # bubble_sort(array)
    # select_sort(array)
    # insert_sort(array)
    quick_sort(array, 0, len(array) - 1)
    print(array)
